#include <iostream>
#include <vector>

#include "common_list.h"

using namespace std;

bool isPalindromeExist(struct ListNode *head) {
    ListNode *pre, *cur, *nxt;
    pre = cur = head;
    if (!head->next)
        return true;
    nxt = head->next;

    while (1) {
        if (cur->val == nxt->val) {
            return true;
        }

        nxt = nxt->next;
        if (!nxt)
            return false;
        cur = cur->next;
        if (pre->val == nxt->val) {
            return true;
        }
        pre = pre->next;

        if (!nxt) {
            break;
        }
    }
    return false;
}

// struct ListNode *pos_seq;
// bool isPalindromeFlag = true;
void do_palindrome(struct ListNode *head, struct ListNode **pos_seq,
                   bool *flag) {
    if (!head) {
        return;
    }
    do_palindrome(head->next, pos_seq, flag);
    if (head->val != (*pos_seq)->val)
        *flag = false;
    *pos_seq = (*pos_seq)->next;
}

bool isPalindrome(struct ListNode *head) {
    struct ListNode *pos_seq;
    bool flag = true;

    pos_seq = head;
    if (!head->next)
        return true;
    do_palindrome(head, &pos_seq, &flag);
    return flag;
}

int main(void) {
    int val[] = {
        0,
    };

    ListNode *head = generate_list_val(sizeof(val) / sizeof(int), val);
    cout << "(回文链表)" << endl;
    print_list(head);
    if (isPalindromeExist(head)) {
        cout << "存在回文链表" << endl;
    } else {
        cout << "不存在回文链表" << endl;
    }

    if (isPalindrome(head)) {
        cout << "是回文链表" << endl;
    } else {
        cout << "不是回文链表" << endl;
    }

    return 0;
}